package nasp.labos.prvi.avltree;

import java.awt.Point;

/**
 * Implementacija AVLTree 
 * implementirana add funkcija koja dodaje elemente
 * @author Stjepan Hadjić
 *
 */
public class AVLTree {	
	
	private Node root;
	private Point maxPoint;
	private int depth;
	private int elements;
	private boolean changed = false;
	
	
	public AVLTree() {
		root = null;
		maxPoint = new Point(400,100);
		depth = 0;
		elements = 0;
	}
	
	public Node getRoot() {
		return root;
	}
	
	public Point getMaxPoint() {
		return maxPoint;
	}
	
	/**
	 * funkcija za pražnjenje stabla
	 */
	public void clear(){
		root = null;
		elements = 0;
		depth = 0;
		maxPoint = new Point(400,100);
	}
	
	/**
	 * funkcija koja odreduje veličinu stabla zbog potreba crtanja
	 * @param node
	 */
	public void setkMaxPoint(Node node){
		if(node.point.x > maxPoint.x)
			maxPoint.x = node.point.x+200;
		if(node.point.y+100 > maxPoint.y)
			maxPoint.y = node.point.y+200;
	}
	
	/**
	 * fukcija koja provjerava najvecu dubinu zbog potreba crtanja
	 * @param node
	 */
	public void setTreeDepth(Node node){
		if(node.depth > depth)
			depth = node.depth;
	}
	
	/**
	 * funkcija koja dodaje element u stablo
	 * @param e
	 */
	public void add(int e){
		add(root, e);
		setTree();
	}
	
	/**
	 * implementacija funkcija add gdje se najprije trazi gdje se taj element nazali
	 * pa nakon toga se provjerava ravnoteza stabla. Ako stablo nije uravnoteženo,
	 * uravnotežava ga se
	 * @param node
	 * @param e
	 */
	private void add(Node node, int e){
		if(node == null)
			root = new Node(e);
		else 
			if (node.element.intValue() < e){
				if(node.right == null){
					node.right = new Node(e);
					elements++;
					node.right.depth = node.depth+1;
					setTreeDepth(node.right);
					node.right.parent = node;
					checkBF(node);
				}
				else
					add(node.right,e);
			}
			else if(node.element.intValue() > e){
				if(node.left == null){
					node.left = new Node(e);
					elements++;
					node.left.depth = node.depth+1;
					setTreeDepth(node.left);
					node.left.parent = node;
					checkBF(node);
				}
				else
					add(node.left,e);
			}
	}
	
	/**
	 * Funkcija koja provjerava ravnotežu stabla
	 * počevši od lista prema korjenu
	 * @param node
	 */
	public void checkBF(Node node){
		setBF(node);
		if(node.balanceFactor == 2 || node.balanceFactor == -2){
			balanceTree(node);
			changed = true;
			return;
		}
		if(node.parent != null)
			checkBF(node.parent);
	}
	
	/**
	 * funkcija koja uravnozežuje podstablo te u ovisnosti o ravnotežnim faktorima
	 * rade se lijee i desne rotacije
	 * @param node
	 */
	public void balanceTree(Node node){
		if(node.balanceFactor == 2){
			if(node.right.balanceFactor == 1)
				leftRotation(node, node.right);
			else
				if(node.right.balanceFactor == -1){
					rightRotation(node.right, node.right.left);
					leftRotation(node, node.right);
				}
		}
		else if(node.balanceFactor == -2){
			if(node.left.balanceFactor == -1)
				rightRotation(node, node.left);
			else
				if(node.left.balanceFactor == 1){
					leftRotation(node.left, node.left.right);
					rightRotation(node, node.left);
				}
		}
	}
	
	/**
	 * Desna rotacija djeteta oko roditelja
	 * @param parent
	 * @param child
	 */
	public void rightRotation(Node parent,Node child){
		if(parent.parent != null){
			if(parent.parent.left == parent)
				parent.parent.left = child;
			else
				parent.parent.right = child;
			child.parent = parent.parent;
		}
		else{
			child.parent = null;
			root = child;
		}
		if(child.right != null){
			parent.left = child.right;
			child.right.parent = parent;
		}
		else
			parent.left = null;
		child.right = parent;
		parent.parent = child;
	}
	
	/**
	 * Lijeva rotacija djeteta oko roditelja
	 * @param parent
	 * @param child
	 */
	public void leftRotation(Node parent, Node child){
		if(parent.parent != null){
			if(parent.parent.right == parent)
				parent.parent.right = child;
			else
				parent.parent.left = child;
			child.parent = parent.parent;
		}
		else{
			child.parent = null;
			root = child;
		}
		if(child.left != null){
			parent.right = child.left;
			child.left.parent = parent;
		}
		else{
			parent.right = null;
		}
		child.left = parent;
		parent.parent = child;
	}
	
	/**
	 * Funkcija koja određuje koordinate svakog elemenata
	 * za potrebe crtanja stabla
	 */
	public void setLocations(){
		int n = (int)Math.pow(2, depth);
		int x = n * 100;
		root.point.x = x/2;
		root.point.y = 100;
		setLocations(root);
	}
	
	/**
	 * Rekurzivna funkcija za odreivanje kooridinata svakog elemenata
	 * @param node
	 */
	public void setLocations(Node node){
		if(node == null)
			return;
		if(node.parent!=null){
			if(node == node.parent.left)
				node.point.x = node.parent.point.x - ((int)Math.pow(2, depth-node.depth))*50;
			if(node == node.parent.right)
				node.point.x = node.parent.point.x + ((int)Math.pow(2, depth-node.depth))*50;
			node.point.y = node.parent.point.y + 100;
		}
		setLocations(node.left);
		setLocations(node.right);
		setkMaxPoint(node);
	}
	
	/**
	 * Funkcija za postavljanje pravih dubina svakom elementu
	 * @param node
	 * @param depth
	 */
	public void setDepths(Node node,int depth){
		if(node == null)
			return;
		node.depth = depth;
		depth ++;
		setTreeDepth(node);
		setDepths(node.left, depth);
		setDepths(node.right, depth);
	}
	
	/**
	 * Funkcija za određivanje ravnotežnog faktora svakog elementa
	 * @param node
	 * @return
	 */
	public int setBF(Node node){
		if(node.left == null && node.right == null){
			node.balanceFactor = 0;
			return node.depth;
		}
		int l = node.depth,r=node.depth;
		if(node.left != null){
			l = setBF(node.left);
		}
		if(node.right != null){
			r = setBF(node.right);
		}
		node.balanceFactor = r - l;
		if( l > r)
			return l;
		else
			return r;
	}
	
	/**
	 * funkcija za pripremu stabla prije crtanja
	 */
	public void setTree(){
		if(changed){
			setDepths(root, 0);
			changed = false;
		}
		setBF(root);
		setLocations();
	}
}
